package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 排序算法的稳定性测试
 * 
 * @author 付大石
 */

public class Main {

    public static void main(String[] args) {

        String[] arr = new String[] { "12-34", "54-34", "54-34", "65-34", "12-34", "54-34", "12-57", "65-57", "54-57",
                "65-57", "54-57", "65-57", "12-57", "65-57", "12-13", "65-13", "54-13", "65-13", "12-13", "54-13",
                "65-13", "54-13" };
        sort(arr, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                int i1 = Integer.parseInt(s1.split("-")[0]);
                int i2 = Integer.parseInt(s2.split("-")[0]);
                return i1 - i2;
            }
        });
        sort(arr, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                int i1 = Integer.parseInt(s1.split("-")[1]);
                int i2 = Integer.parseInt(s2.split("-")[1]);
                return i1 - i2;
            }
        });
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 使用稳定的插入排序
     * 
     * @param arr
     * @param comp
     */
//    public static void sort(String[] arr, Comparator<String> comp) {
//
//        for (int i = 1; i < arr.length; i++) {
//            int j = i;
//            String temp = arr[j];
//            while (j > 0 && comp.compare(temp, arr[j - 1]) < 0) {
//                arr[j] = arr[j - 1];
//                j--;
//            }
//            arr[j] = temp;
//        }
//    }
//    12-13
//    12-13
//    54-13
//    54-13
//    54-13
//    65-13
//    65-13
//    65-13
//    12-34
//    12-34
//    54-34
//    54-34
//    54-34
//    65-34
//    12-57
//    12-57
//    54-57
//    54-57
//    65-57
//    65-57
//    65-57
//    65-57

    /**
     * 使用不稳定的选择排序
     * 
     * @param arr
     * @param comp
     */
    public static void sort(String[] arr, Comparator<String> comp) {

        for (int i = 0; i < arr.length - 1; i++) {
            String min = arr[i];
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (comp.compare(min, arr[j]) > 0) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            String temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
//    12-13
//    12-13
//    54-13
//    54-13
//    54-13
//    65-13
//    65-13
//    65-13
//    54-34
//    54-34
//    12-34
//    12-34
//    54-34
//    65-34
//    65-57
//    54-57
//    65-57
//    12-57
//    65-57
//    12-57
//    54-57
//    65-57
}